A two-dimensional array, or matrix, is a data structure that is frequently used in computing to store various data objects. For example, digital pictures are generally stored in memory as two-dimensional arrays, each element of the array representing a pixel having coordinates corresponding to a particular column and row. It is not uncommon that an array needs to be rotated clockwise, or counter-clockwise, by 90°. For example, a digital photograph taken in portrait format may need to be rotated by 90° in order for it to be properly displayed. Many portable data devices, such as personal digital assistants, mobile phones, and global positioning systems, are designed with displays that can be viewed in both portrait and landscape orientations. Consequently, it is necessary for these devices to be able to quickly and efficiently rotate the display matrix as a user switches between portrait and landscape orientations.
Traditionally, rotating an array has been accomplished via a brute force of copying the array, element by element, to a new memory locations. For example, in the case of a digital image, the bits representing the color for each pixel (i.e., pixel data) are individually read from memory and written to a temporary buffer. Then, a target memory location for the rotated image is determined for the pixel data stored in the temporary buffer. Finally, the pixel data stored in the temporary buffer is copied to the target memory location. Once the pixel data for each pixel in the image has been read, temporarily stored, and then written to the target location, the rotated image is ready to be displayed.
The problem with this traditional approach is that it is costly in terms of processor and memory resources. For example, using the traditional approach to rotate an N×N array, N2 load operations and N2 store operations are required, resulting in 2N2 total operations. Consequently, a more efficient method of rotating arrays is desirable.